Orthogonal transformations, i.e. mirror and rotate operations, are frequently omitted from bitmap graphics systems, because they are computationally intensive, require a large number of memory references and considerable bit shifting. These difficulties are primarily due to the frame buffer organization in bitmap graphics systems. The frame buffer is used for refreshing raster scan display devices in addition to image data storage, so it is usually organized in raster scan order. Typically, Pixel vectors can only be accessed by row, not by column, and only at word boundaries. Thus, all of the usual image transformations except the identity transformation, which requires no bitmap word moves, and the mirror transformation along the x-axis, which only requires exchanging words on corresponding rows, are difficult to perform.
Several ways to rotate an image have been developed. In one rotation, using an image shearing algorithm, a sequence of shearing operations are made. Each shear operation operates on each column or row of a matrix by progressively large amounts. To perform a 90 degree counterclockwise rotation, for example, three shear operations, shear horizontally right from top, shear vertically down from right, and shear horizontally left from bottom, are used.
Using a recursive permutation algorithm for rotation, progressively larger pieces of the image are permuted or rotated. The first step is to divide the image into groups of two by two pixel matrices. Each matrix is permuted. To perform a 90 degree counterclockwise rotation, for example, the upper right pixel of each matrix moves to the upper left position, each upper left pixel moves to the lower left position of the matrix, the lower left pixels move to the lower right positions, and the lower right pixel of each matrix moves to the upper right position. The second step treats each two by two permuted matrix as a unit and divides the matrix into four by four pixel matrices, i.e., four two by two units. Each of these four by four matrices is permuted. The top right two by two unit is moved left, and so forth. The next step uses the four by four matrices as units. The sequence is repeated until the entire matrix is rotated.
In U.S. Pat. No. 4,052,699 to Micka et al, an image processing system rotates an image 90 degrees clock-wise by first sequentially loading image data in parallel by row into an n by n matrix, where each word is n bits long. The matrix is then unloaded sequentially in parallel by column into an array of n word length shift registers. The result is n vertical words each composed of n bits from a given bit position in each register. Output words are then stored in an external image memory for subsequent accessibility.
The primary advantage of the first two algorithms is that they both transform the image in situ so that temporary storage is not required. However, the organization of bitmap memory makes their implementation difficult. The shearing algorithm requires several memory operations per pixel. The vertical shear used in the image shearing rotation algorithm is awkward, because it requires accessing and shifting columns of vectors. The first step, involving two by two matrices, in the recursive permutation algorithm requires approximately one memory operation per pixel. Each subsequent step accesses each pixel at least once. So, the recursive permutation algorithm requires log n memory operations per pixel, where n is the number of pixels along the longest edge of the image being rotated.
Accordingly, it is an object of the invention to produce a system for performing orthogonal transformations which is fast and easy to implement with conventional bitmap memories.
It is another object of the invention to produce a method in which orthogonal transformations are performed directly without large amounts of extra memory, permuting progressively larger pieces of image, shifting or shearing.